package 线段树And树状数组;
/**
 * 左程云 那个   
 * 问题 一：俄罗斯 方块的 问题   
 *1. 离散 化  映射  
 *2，线段树 模型 
 * 
 * 问题二： 最多线段 重合问题 
 * 
 * 
 * 
 * 
 * 
 * 问题三 ：  涂 染料     问题 
 * 
 * 这些 都是 相关的  线段树问题
 * @author I adore you
 *
 */
public class SegmentTree {
	public static void main(String []args) {
//		System.out.println(1+1<<1);
		int nums[] = {1,2,3,4,5};
		System.out.println(recursionGetArraySum(nums,0,nums.length-1));
	}
	/**
	 * 递归 求  数组的 和    (l+r)/2 =mid    左边是 [l,mid]  右边 是 [mid+1,r] 如果写成 [mid , r] 会死循环 
	 * 其实  找两个相邻的数   一测试 就明白了  相邻的 数  测试 一下    因为 / 这个运算符号 是 默认向下 取整的
 	 * 这里 有个 小的 细节在  这里
	 * @param nums
	 * @param l
	 * @param r
	 * @return
	 */
	public static int recursionGetArraySum(int nums[],int l,int r) {
		if(l == r) {
			return nums[l];
		}  
		//  这些 中间变量 可有 可无
//		int sum=0;
//		sum+=recursionGetArraySum(nums,l,l+((r-l)>>1));
//		sum+=recursionGetArraySum(nums,l+((r-l)>>1)+1,r);
//		sum+=recursionGetArraySum(nums,(l+r)/2+1,r);
//		sum+=recursionGetArraySum(nums,l,(l+r)/2);
//		return sum;
		return recursionGetArraySum(nums,l,l+((r-l)>>1))+recursionGetArraySum(nums,l+((r-l)>>1)+1,r);
	}
}
